0% completed
Problem Statement
You are given a prices array containing the integers, where price[i] refers to the stock price on ith day.
You are allowed to do as many transactions as you like (buy one and sell one stock multiple times). You cannot engage in multiple transactions simultaneously (you must sell the stock before you buy again). However, you can buy again on the same day after selling.
Find the maximum profit you can achieve from these transactions.
Examples
-
Example 1:
- Input:
[4, 9, 2, 3, 6, 8] - Expected Output:
11 - Justification: Buy on day 1 (price = 4) and sell on day 2 (price = 9), profit = 9-4 = 5. Then buy on day 3 (price = 2) and sell on day 6 (price = 8), profit = 8-2 = 6. Total profit is 5 + 6 = 11.
- Input:
-
Example 2:
- Input:
[5, 3, 6, 2, 5, 4] - Expected Output:
6 - Justification: Buy on day 2 (price = 3) and sell on day 3 (price = 6), profit = 6-3 = 3. Then buy on day 4 (price = 2) and sell on day 5 (price = 5), profit = 5-2 = 3. Total profit is 3 + 3 = 6.
- Input:
-
Example 3:
- Input:
[10, 8, 6, 5, 4, 2] - Expected Output:
0 - Justification: Prices are decreasing each day, so there's no opportunity to make a profit. It is best not to make any transactions.
- Input:
Solution
To solve this problem, we'll adopt a greedy approach, focusing on capturing every possible profitable transaction. The key idea is to accumulate profit from every upward trend, which is identified by buying at the start of the trend (local minimum) and selling at the end (local maximum). This strategy ensures we don't miss any profit opportunity by trying to predict the highest peak or lowest valley ahead of time.
This approach is effective because it capitalizes on the fact that the sum of profits from each consecutive transaction (buy low, sell high) adds up to the maximum possible profit. It aligns with the principle of taking advantage of every positive price difference between consecutive days. By summing up all positive differences, we can maximize the profit without needing to know the overall price pattern in advance.
Step-by-step Algorithm
- Initialize
totalProfitto 0. - Iterate through the price array from the first day to the last day.
- For each day, compare the current day's price to the previous day's price.
- If the current day's price is higher than the previous day's price:
- Calculate the difference (profit) and add it to
totalProfit.
- Calculate the difference (profit) and add it to
- Return
totalProfitas the maximum profit that can be achieved.
5. Algorithm Walkthrough
Let's consider the input [5, 3, 6, 2, 5, 4]:
-
Initialization:
- Start with
totalProfit = 0. - The input prices are
[5, 3, 6, 2, 5, 4].
- Start with
-
Day 1 to Day 2:
- Prices move from 5 to 3. There's no profit since the price decreased, so we do nothing.
totalProfitremains0.
-
Day 2 to Day 3:
- Prices move from 3 to 6. This is a profitable move.
- Buy at 3 and sell at 6, making a profit of
6 - 3 = 3. - Update
totalProfitto3.
-
Day 3 to Day 4:
- Prices move from 6 to 2. Price decreased, so we do nothing.
totalProfitis still3.
-
Day 4 to Day 5:
- Prices move from 2 to 5. Another opportunity to profit.
- Buy at 2 and sell at 5, making a profit of
5 - 2 = 3. - Update
totalProfitto3 + 3 = 6.
-
Day 5 to Day 6:
- Prices move from 5 to 4. Price decreased, so we do nothing.
totalProfitremains6.
-
Conclusion:
- By the end of the last trading day, we've captured all profitable transactions by buying low and selling high.
- The final
totalProfitis6.
Code
Complexity Analysis
Time Complexity
: The algorithm iterates through the array of stock prices exactly once. Here, nrepresents the number of days for which we have stock prices.
Space Complexity
: The algorithm uses a fixed amount of extra space to store variables ( totalProfitand loop indexi). This usage does not scale with the input size, making the space complexity constant.
On this page
Problem Statement
Examples
Solution
Step-by-step Algorithm
- Algorithm Walkthrough
Code
Complexity Analysis
Time Complexity
Space Complexity